/************************************************************************
                                                                     
   Xceed Ultimate ListBox for Silverlight                                                                                                                                            
   Copyright (C) 2010 Xceed Software Inc.    
                                                                     
   This program is provided to you under the terms of the GNU General Public  
   License version 2 as published by the Free Software Foundation. 
        
   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY, without even the implied warranty of 
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License along 
   with this program, if not, write to the Free Software Foundation, Inc., 
   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

   This program can be provided to you by Xceed Software Inc. under a
   proprietary commercial license agreement for use in non-Open Source
   projects. Visit Xceed.com to find the commercial edition of 
   Xceed Ultimate ListBox for Silverlight.                                    
                                                                      
 **********************************************************************/

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace Xceed.Silverlight.Data
{
  public sealed class DynamicBufferConfiguration : BufferConfiguration
  {
    #region Static Fields

    private const int HistoryLength = 50;

    private const int MinimumBufferCapacity = 10;
    private const int MaximumBufferCapacity = 5000;

    private const int MinimumActivePreFetchSize = 5;
    private const int MaximumActivePreFetchSize = 1000;

    private const int MinimumPassivePreFetchSize = 0;
    private const int MaximumPassivePreFetchSize = 250;

    private const double ActivePreFetchSizeBoostRatio = 1.25d;

    private const double ShrinkThresholdRatio = 0.2d;
    private const double ShrinkRatio = 0.2d;
    private const int ShrinkCountToReleaseItems = 20;

    private static readonly TimeSpan SpareTime = TimeSpan.FromSeconds( 5d );

    #endregion

    #region Constructor

    public DynamicBufferConfiguration()
    {
    }

    public DynamicBufferConfiguration(
      int minimumBufferCapacity,
      int maximumBufferCapacity )
      : this()
    {
      m_minimumBufferCapacity = minimumBufferCapacity;
      m_maximumBufferCapacity = maximumBufferCapacity;
    }

    public DynamicBufferConfiguration(
      int minimumBufferCapacity,
      int maximumBufferCapacity,
      int minimumActivePreFetchSize,
      int maximumActivePreFetchSize )
      : this( minimumBufferCapacity, maximumBufferCapacity )
    {
      m_minimumActivePreFetchSize = minimumActivePreFetchSize;
      m_maximumActivePreFetchSize = maximumActivePreFetchSize;
    }

    public DynamicBufferConfiguration(
      int minimumBufferCapacity,
      int maximumBufferCapacity,
      int minimumActivePreFetchSize,
      int maximumActivePreFetchSize,
      int minimumPassivePreFetchSize,
      int maximumPassivePreFetchSize )
      : this( minimumBufferCapacity, maximumBufferCapacity, minimumActivePreFetchSize, maximumActivePreFetchSize )
    {
      m_minimumPassivePreFetchSize = minimumPassivePreFetchSize;
      m_maximumPassivePreFetchSize = maximumPassivePreFetchSize;
    }

    #endregion

    internal override void Initialize( BufferInfo bufferInfo )
    {
      bufferInfo.SetRequestsHistoryLength( DynamicBufferConfiguration.HistoryLength );

      bufferInfo.SetCapacityRange( m_minimumBufferCapacity, m_maximumBufferCapacity );
      bufferInfo.SetActivePreFetchingSizeRange( m_minimumActivePreFetchSize, m_maximumActivePreFetchSize );
      bufferInfo.SetPassivePreFetchingSizeRange( m_minimumPassivePreFetchSize, m_maximumPassivePreFetchSize );

      bufferInfo.State = new Storage();
    }

    internal override int GetActivePreFetchSize( BufferInfo bufferInfo )
    {
      int fetchSize = DynamicBufferConfiguration.GetStorage( bufferInfo ).ActivePreFetchSize;

      // If the buffer contains a lot of free space, try to boost the active pre-fetch size
      // in order to fill out those spaces quicker.
      int emptySpace = bufferInfo.Capacity - bufferInfo.Size;
      if( emptySpace > fetchSize )
      {
        fetchSize = ( int )Math.Ceiling( fetchSize * DynamicBufferConfiguration.ActivePreFetchSizeBoostRatio );
      }

      return fetchSize;
    }

    internal override int GetPassivePreFetchSize( BufferInfo bufferInfo )
    {
      return DynamicBufferConfiguration.GetMaximumFetchSize( bufferInfo.RequestsHistory );
    }

    internal override int GetBufferCapacity( BufferInfo bufferInfo )
    {
      // Find an estimation of the number of items that is required per second.
      double consumptionRate = DynamicBufferConfiguration.GetConsumptionRate( bufferInfo );
      bool isStagnant = ( consumptionRate <= 0d );

      // Find out the desired time it would take to consume the whole buffer
      // if there was no pre-fetching.
      double spareTimeInSeconds = DynamicBufferConfiguration.GetSpareTimeInSeconds();

      // Find out the maximum fetch size requested by the client.
      int maximumFetchSize = DynamicBufferConfiguration.GetMaximumFetchSize( bufferInfo.RequestsHistory );

      // Find out the number of items we must have to fill out the requests for a given period of time.
      int requiredCapacity = ( isStagnant )
                               ? ( int )Math.Ceiling( maximumFetchSize * spareTimeInSeconds )
                               : ( int )Math.Ceiling( consumptionRate * spareTimeInSeconds );

      // Find out the response time of the data source.
      TimeSpan responseTime = DynamicBufferConfiguration.GetResponseTime( bufferInfo );

      // Find out the active pre-fetch size based on the consumption rate.
      int activePreFetchSize = ( int )Math.Ceiling( consumptionRate * responseTime.TotalSeconds * DynamicBufferConfiguration.ActivePreFetchSizeBoostRatio );

      // Store the active pre-fetch size for further use.
      Storage storage = DynamicBufferConfiguration.GetStorage( bufferInfo );
      storage.MaximumFetchSize = Math.Max( storage.MaximumFetchSize, maximumFetchSize );
      storage.ActivePreFetchSize = ( isStagnant )
                                     ? Math.Max( storage.ActivePreFetchSize, maximumFetchSize )
                                     : activePreFetchSize;

      // Extend the required capacity to create a free space where the pre-fetched items
      // may be placed.
      requiredCapacity += activePreFetchSize;

      // The required capacity doesn't take into account the fact that the buffer has a 
      // center of gravity which may lower the expected capacity.  We must boost the 
      // required capacity here in order to counter the effect of the center of gravity.
      int capacity = DynamicBufferConfiguration.ExtendBufferCapacity( bufferInfo, requiredCapacity );
      capacity = Math.Max( capacity, storage.MaximumFetchSize );

      // Since the client isn't consuming any data right now, keep the
      // buffer as it is except if we think it would be better to enlarge it
      // based on past experience.
      if( isStagnant )
      {
        capacity = Math.Max( capacity, bufferInfo.Capacity );
      }
      // The client is consuming some of the items that are in the buffer.
      // Allow the buffer to shrink if it way too large for the current
      // consumption rate.
      else
      {
        // If the new capacity is lower than the current buffer size, minimize the number of
        // items lost just in case the buffer will increase again next time.
        capacity = DynamicBufferConfiguration.ShrinkBufferCapacity( bufferInfo, capacity );
      }

      return capacity;
    }

    private static Storage GetStorage( BufferInfo bufferInfo )
    {
      Storage storage = bufferInfo.State as Storage;
      Debug.Assert( storage != null );

      return storage;
    }

    private static double GetConsumptionRate( BufferInfo bufferInfo )
    {
      Storage storage = DynamicBufferConfiguration.GetStorage( bufferInfo );

      // Find an estimation of the number of items that is required per second.
      double consumptionRate = DynamicBufferConfiguration.GetItemsConsumedPerSecond( bufferInfo );

      // No items have been requested during a period of time.  Use an old comsumption rate.
      if( consumptionRate <= 0d )
      {
        // We have no idea of the consumption rate.  Take the an old consumption rate instead.
        if( storage.ConsumptionRate.HasValue )
        {
          consumptionRate = storage.ConsumptionRate.Value;
        }
      }
      else
      {
        storage.ConsumptionRate = consumptionRate;
      }

      return consumptionRate;
    }

    private static TimeSpan GetResponseTime( BufferInfo bufferInfo )
    {
      Storage storage = DynamicBufferConfiguration.GetStorage( bufferInfo );

      // Find out the number of items the data source may transfer per second.
      TimeSpan responseTime = DynamicBufferConfiguration.GetResponseTime( bufferInfo.RequestsHistory );

      if( responseTime <= TimeSpan.Zero )
      {
        responseTime = storage.ResponseTime.GetValueOrDefault( TimeSpan.Zero );
      }
      else
      {
        storage.ResponseTime = responseTime;
      }

      return responseTime;
    }

    private static double GetSpareTimeInSeconds()
    {
      double spareTimeInSeconds = DynamicBufferConfiguration.SpareTime.TotalSeconds;

      return Math.Max( spareTimeInSeconds, 0d );
    }

    private static int ExtendBufferCapacity( BufferInfo bufferInfo, int minimumCapacity )
    {
      double centerOfGravity = bufferInfo.CenterOfGravity;
      int capacity;

      if( ( centerOfGravity > 0d ) && ( centerOfGravity < 1d ) )
      {
        double centerOfGravityRatio = Math.Max( centerOfGravity, 1d - centerOfGravity );
        double newCapacity = minimumCapacity / centerOfGravityRatio;

        if( ( !double.IsNaN( newCapacity ) ) && ( !double.IsInfinity( newCapacity ) ) )
        {
          capacity = ( newCapacity > int.MaxValue ) ? int.MaxValue : ( int )Math.Ceiling( newCapacity );
        }
        else
        {
          capacity = minimumCapacity;
        }
      }
      else
      {
        capacity = minimumCapacity;
      }

      return capacity;
    }

    private static int ShrinkBufferCapacity( BufferInfo bufferInfo, int maximumCapacity )
    {
      Storage storage = DynamicBufferConfiguration.GetStorage( bufferInfo );
      int capacity = Math.Max( maximumCapacity, bufferInfo.Capacity );

      // The request capacity is lower than the number of items in the buffer.
      // We'll have to lose some items in order to shrink the buffer.
      if( maximumCapacity < bufferInfo.Size )
      {
        int shrinkDifference = ( int )Math.Floor( bufferInfo.Capacity * DynamicBufferConfiguration.ShrinkThresholdRatio );

        // Prevent the buffer from shrinking since the change is insignificant.
        if( maximumCapacity > bufferInfo.Capacity - shrinkDifference )
        {
          storage.ShrinkCount = 0;
        }
        // The buffer was asked to shrink many times.  Shrink it now even if it means
        // losing items.
        else if( storage.ShrinkCount >= DynamicBufferConfiguration.ShrinkCountToReleaseItems )
        {
          int shrinkSize = ( int )Math.Ceiling( ( bufferInfo.Capacity - maximumCapacity ) * DynamicBufferConfiguration.ShrinkRatio );

          capacity -= shrinkSize;
          storage.ShrinkCount = 0;
        }
        // Do no shrink the buffer yet.  It may grow back again in a few queries.
        // We want to avoid to requery for the same items as most as possible.
        else
        {
          storage.ShrinkCount++;
        }
      }
      else
      {
        storage.ShrinkCount = 0;
      }

      return capacity;
    }

    private static int GetMaximumFetchSize( IEnumerable<BufferRequestInfo> requestsHistory )
    {
      int maximum = 0;

      foreach( BufferRequestInfo request in requestsHistory )
      {
        PassivePreFetchingBufferRequestInfo passiveRequest = request as PassivePreFetchingBufferRequestInfo;

        if( passiveRequest != null )
        {
          maximum = Math.Max( maximum, passiveRequest.FetchSize );
        }
      }

      return maximum;
    }

    private static double GetItemsConsumedPerSecond( BufferInfo bufferInfo )
    {
      DateTime now = DateTime.Now;
      List<BufferRequestInfo> requestsHistory = ( from ri in bufferInfo.RequestsHistory
                                                  where !( ri is ActivePreFetchingBufferRequestInfo )
                                                      && ( now.Subtract( ri.TimeStamp ) <= DynamicBufferConfiguration.SpareTime )
                                                  orderby ri.TimeStamp descending
                                                  select ri ).ToList();
      double consumptionRate = 0d;

      // There is at least a request we can use.
      if( requestsHistory.Count > 0 )
      {
        requestsHistory.ForEach( ( ri ) => consumptionRate += ri.FetchSize );

        // Find out the elapsed time.
        TimeSpan interval = now.Subtract( requestsHistory.Last().TimeStamp );
        // Prevent the consumption rate from exploding if the time interval is too short.
        double intervalInSeconds = Math.Max( 0.1d, interval.TotalSeconds );

        if( ( requestsHistory.Count > 1 ) || ( intervalInSeconds >= 1d ) )
        {
          // Make sure the time interval is big enough to get an appropriate estimation.
          consumptionRate /= Math.Min( intervalInSeconds, requestsHistory.Count );
        }
      }

      return consumptionRate;
    }

    private static TimeSpan GetResponseTime( IEnumerable<BufferRequestInfo> requestsHistory )
    {
      TimeSpan passiveResponseTime = DynamicBufferConfiguration.GetAverageResponseTime( ( from ri in requestsHistory
                                                                                          where ( ri is PassivePreFetchingBufferRequestInfo )
                                                                                          select ri.ResponseTime ) );
      TimeSpan activeResponseTime = DynamicBufferConfiguration.GetAverageResponseTime( ( from ri in requestsHistory
                                                                                         where ( ri is ActivePreFetchingBufferRequestInfo )
                                                                                         select ri.ResponseTime ) );

      if( passiveResponseTime <= TimeSpan.Zero )
      {
        return activeResponseTime;
      }
      else if( activeResponseTime <= TimeSpan.Zero )
      {
        return passiveResponseTime;
      }
      else
      {
        return TimeSpan.FromSeconds( ( activeResponseTime + passiveResponseTime ).TotalSeconds / 2 );
      }
    }

    private static TimeSpan GetAverageResponseTime( IEnumerable<TimeSpan> responseTimes )
    {
      TimeSpan sum = TimeSpan.Zero;
      int count = 0;

      foreach( TimeSpan responseTime in responseTimes )
      {
        sum += responseTime;
        count++;
      }

      if( count <= 1 )
        return sum;

      return TimeSpan.FromMilliseconds( sum.TotalMilliseconds / count );
    }

    #region Private Fields

    private int m_minimumBufferCapacity = DynamicBufferConfiguration.MinimumBufferCapacity;
    private int m_maximumBufferCapacity = DynamicBufferConfiguration.MaximumBufferCapacity;
    private int m_minimumActivePreFetchSize = DynamicBufferConfiguration.MinimumActivePreFetchSize;
    private int m_maximumActivePreFetchSize = DynamicBufferConfiguration.MaximumActivePreFetchSize;
    private int m_minimumPassivePreFetchSize = DynamicBufferConfiguration.MinimumPassivePreFetchSize;
    private int m_maximumPassivePreFetchSize = DynamicBufferConfiguration.MaximumPassivePreFetchSize;

    #endregion

    #region Private Storage Nested Type

    private class Storage
    {
      internal Nullable<double> ConsumptionRate;
      internal Nullable<TimeSpan> ResponseTime;
      internal int ActivePreFetchSize;
      internal int MaximumFetchSize;
      internal int ShrinkCount;
    }

    #endregion
  }
}
